package com.hy;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:滑动窗口最大值
 * author: Mr.Du
 * Date: 2023/9/25
 * Time: 16:32
 */
public class MaxSlidingWindow {

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }

        int n = nums.length;
        int[] result = new int[n - k + 1];
        int resultIndex = 0;

        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // 移除超出窗口范围的元素
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }

            // 移除队列尾部小于当前元素的元素
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }

            // 将当前元素的索引加入队列
            deque.offer(i);

            // 计算窗口的最大值并存入结果数组
            if (i >= k - 1) {
                result[resultIndex++] = nums[deque.peek()];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        MaxSlidingWindow maxSlidingWindow = new MaxSlidingWindow();
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int[] res = maxSlidingWindow.maxSlidingWindow(nums, 3);
        System.out.println(Arrays.toString(res));

    }
}
